|
In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky. The simplest description of the correspondence is using the Schensted algorithm , a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction. The correspondence had been described, in a rather different form, much earlier by Robinson , in an attempt to prove the Littlewood–Richardson rule. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted–algorithm, and almost entirely forgotten. Other methods of defining the correspondence include a nondeterministic algorithm in terms of jeu de taquin. The bijective nature of the correspondence relates it to the enumerative identity: : where denotes the set of partitions of (or of Young diagrams with squares), and denotes the number of standard Young tableaux of shape . == The Schensted algorithm == The Schensted algorithm starts from the permutation written in two-line notation : where , and proceeds by constructing sequentially a sequence of (intermediate) ordered pairs of Young tableaux of the same shape: : where are empty tableaux. The output tableaux are and . Once is constructed, one forms by ''inserting'' into , and then by adding an entry to in the square added to the shape by the insertion (so that and have equal shapes for all ). Because of the more passive role of the tableaux , the final one , which is part of the output and from which the previous are easily read off, is called the recording tableau; by contrast the tableaux are called insertion tableaux. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Robinson–Schensted correspondence」の詳細全文を読む スポンサード リンク
|